package com.lili.dt;

/**
 * @Auther: 李 力
 * @Date: 2024/8/13
 * @Description: 旅行商问题
 * @version: 1.0
 */
public class Travel {

    /*
     * 描述:有多个城市互通，城市之间的花费不一样，一个商人必须经过各个城市售卖东西
     *      问怎么样才能花费最少？
     *
     *      走完所有城市的走法有(n-1)!种走法
     * */
    public static int getMinMoney(int[][] citys) {
        int m = citys.length;
        /*
         * 列用十进制表示，看作二进制的集合
         * */
        int n = 1 << (m - 1);//剩余城市的组合数 2^(m-1)
        int[][] dp = new int[m][n];
        //填充第0列
        for (int k = 0; k < m; k++) {
            dp[k][0] = citys[k][0];
        }

        //填充后序列
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                dp[i][j] = Integer.MAX_VALUE / 2;
                if (contains(j, i)) {
                    continue;
                } else {
                    //填充单元格
                    for (int k = 0; k < m; k++) {
                        if (contains(j, k)) {
                            dp[i][j] = Math.min(dp[i][j], citys[i][k] + dp[k][exclude(j, k)]);
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    }

    //检查set中是不是包含了city
    private static boolean contains(int set, int city) {
        return (set >> (city - 1) & 1) == 1;
    }

    private static int exclude(int set, int city) {
        return set ^ (1 << (city - 1));
    }
}
